#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size(), one_max = nums1[0] * nums2[0];
        bool zero = (nums1[0] == 0 && nums2[0] == 0);
        vector<vector<int>> dp(n1, vector<int>(n2));
        dp[0][0] = max(0, nums1[0] * nums2[0]);
        for (int j = 1; j < n2; j++) {
            dp[0][j] = max(dp[0][j - 1], max(0, nums1[0] * nums2[j]));
            one_max = max(one_max, nums1[0] * nums2[j]);
            if (nums1[0] != 0 && nums2[j] != 0) zero = false;
        }

        for (int i = 1; i < n1; i++)
            for (int j = 0; j < n2; j++) {
                if (j == 0) dp[i][j] = max(dp[i - 1][j], nums1[i] * nums2[j]);
                else dp[i][j] = max(dp[i - 1][j], max(dp[i - 1][j - 1] + nums1[i] * nums2[j], dp[i][j - 1]));
                one_max = max(one_max, nums1[i] * nums2[j]);
                if (nums1[i] != 0 && nums2[j] != 0) zero = false;
            }
        // for(int i = 0; i < n1; i++) {
        //     for(int j = 0; j < n2; j++) cout << dp[i][j] << ' ';
        //     cout << endl;
        // }
        if (zero) return 0;
        if (!dp[n1 - 1][n2 - 1]) return one_max;
        return max(dp[n1 - 1][n2 - 1], one_max);
    }
};